#include <stdio.h>
#include <malloc.h> 
typedef struct node2{
	int data;             // 数据域 
	struct node2 * pNext;  // 后针域 
	struct node2 * pPre;   // 前指针
} NODE2,* PNODE2;

PNODE2 list_init();           // 初始化
int list_addH(PNODE2 ,int);   // 头追加
int list_addL(PNODE2 ,int);   // 尾追加
int list_delete(PNODE2 ,int ,PNODE2); // 删除单个结点
void traverse_list(PNODE2 );  // 遍历输出 
bool isEmpty(PNODE2 );        // 判断链表是否为空
PNODE2 get_node(PNODE2 ,int); // 获取结点
int list_len(PNODE2 pHead);	  // 求链表长度
void QuickSort(PNODE2 head,PNODE2 foot){
	PNODE2 i,j;
	int k;
	if(head == foot) return ;
	i = head; j = foot;
	k = head->data;
	while(i != j){       //此次划分完成
		while(j != i && j->data > k) j=j->pPre; //从后往前找比k小的
		if (j != i){    
			i->data = j->data;     //比k小的放k前面
			i=i->pNext;
		}
		while(i != j && i->data < k) i=i->pNext; //从前往后找比k大的 
		if(i != j) {
			j->data = i->data;       // 比k大的放k后面 
			j=j->pPre;
		}
	}
	i->data = k;
	/*
	左右子弟归不能同时遍历 
	 */
	if (i->pNext != NULL)
		QuickSort(i->pNext,foot); // 将k右侧再次进行划分
	if (i->pPre != NULL)
		QuickSort(head,i->pPre);  // 将k左侧再次进行划分
	return ;
}

int main(){
	PNODE2 listDat = list_init();
	NODE2 tempN;
	list_addL(listDat,1);
	list_addL(listDat,4);
	list_addH(listDat,2);
	list_addH(listDat,3);
	list_addH(listDat,89);
	list_addH(listDat,23);
	list_addH(listDat,22);
	list_addL(listDat,110);
	list_addL(listDat,28);
	list_addL(listDat,44);
	list_addL(listDat,80);
	traverse_list(listDat);
	// list_delete(listDat,3,&tempN);
	// printf("del: %d\n",tempN.data);
	// traverse_list(listDat);
	// printf("len : %d\n",list_len(listDat));
	// PNODE2 pH,pL;
	// pH = listDat->pNext; pL=get_node(listDat,list_len(listDat));
	// QuickSort(pH,pL);
	// traverse_list(listDat);
	return 0;
}

/**
 * 初始化双链
 * @Author   smallcatx0
 * @DateTime 2017-03-28
 * @return   头指针
 */
PNODE2 list_init(){ 
	PNODE2 pHead = (PNODE2)malloc(sizeof(NODE2));
	if(NULL == pHead){
		printf("malloc ERROR\n");
		exit(-1); 
	}
	pHead->pNext = NULL;
	pHead->pPre  = NULL;
	return pHead; 
}
/**
 * 双链头部添加
 * @Author   smallcatx0
 * @DateTime 2017-03-28
 * @param    pHead      [头结点地址]
 * @param    val        [插入值]
 * @return   bool
 */
int list_addH(PNODE2 pHead,int val){
	PNODE2 pNew = (PNODE2)malloc(sizeof(NODE2));
	if(NULL == pNew) return -1;
	pNew->data = val;

	pNew->pNext = pHead->pNext; 
	pHead->pNext = pNew;
	pNew->pPre = pHead;
	if (pNew->pNext != NULL)
		pNew->pNext->pPre = pNew;

	return true;
}

/**
 * 双链尾添加
 * @Author   smallcatx0
 * @DateTime 2017-03-28
 * @param    pHead      [头结点地址]
 * @param    val        [添加值]
 * @return   bool
 */
int list_addL(PNODE2 pHead,int val){
	PNODE2 p,pLast;   // 当前节点 尾节点 
	// 申请节点组织数据 
	p =(PNODE2)malloc(sizeof(NODE2));
	if( p == NULL) return false; 
	p->data = val;
	p->pNext = NULL;
	p->pPre  = NULL;
	//找到尾节点 
	pLast = get_node(pHead,list_len(pHead)); 
	pLast->pNext = p;
	p->pPre = pLast;
	return true;
}

/**
 * 获取一个结点的值
 * @Author   smallcatx0
 * @DateTime 2017-03-28
 * @param    pHead      [头结点地址]
 * @param    i          [查找位置]
 * @return              [单个结点]
 */
PNODE2 get_node(PNODE2 pHead,int i){
	//初始化条件 从头查找 
	int j = 0;
	PNODE2 p = pHead;
	while(p->pNext && j<i){
		p = p->pNext;
		j++;
	}
	if(i == j)  return p;     // 找到了返回该节点的指针 
	else        return NULL;  // 未找到返回NULL; 
}

/**
 * 求链表长度
 * @Author   smallcatx0
 * @DateTime 2017-03-28
 * @param    pHead      [头结点地址]
 * @return   int        [链表长度]
 */
int list_len(PNODE2 pHead){
	int len =0 ;
	if(isEmpty(pHead))  return 0;
	
	PNODE2 p = pHead;
	while(NULL != p->pNext){   // 遍历一个链表 
		len++;
		p = p->pNext;
	}
	return len;
}

/**
 * 遍历链表
 * @Author   smallcatx0
 * @DateTime 2017-03-28
 * @param    pHead      [头结点位置]
 */
void traverse_list(PNODE2 pHead){
	if(isEmpty(pHead)){
		printf("list is Empty\n");
		return ;	
	} 
	PNODE2 pNow = pHead->pNext;
	while(NULL != pNow){
		printf("%d ",pNow->data); // 输出当前节点数据 
		pNow = pNow->pNext;       // 下移节点 
	}
	printf("\n");
	return ;
} 

/**
 * 判断链表是否为空
 * @Author   smallcatx0
 * @DateTime 2017-03-28
 * @param    pHead      [头结点地址]
 * @return   bool
 */
bool isEmpty(PNODE2 pHead){
	if(pHead->pNext == NULL)  return true; 
	else     	return false;
} 

int list_delete(PNODE2 pHead,int pos,PNODE2 val){
	PNODE2 pNow = get_node(pHead,pos);       // 待删除元素 
	if(pNow == NULL){         // 判断是否下标是否合法 
		printf("\nERROR:keyOut\n");
		return 0; 
	}
	
	*val = *pNow;                     // 保存待删除的数据 
	pNow->pPre->pNext = pNow->pNext; 
	pNow->pNext->pPre = pNow->pPre;
	free(pNow);                       // 释放内存  
	return 1; 
} 
